/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.dp;

/**
 * <p>
 * 数字解码
 * 
 * 例如：'A' -> 1 'B' -> 2 ... 'Z' -> 26
 * 输入 "12", it could be decoded as "AB" (1 2) or "L" (12).
 * 输出：2 
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年5月30日
 */
public class DecodeWays {
  public int numDecodings(String s) {
        if(s.length()==0){
            return 0;
        }
        int len = s.length();
        int []dp = new int[len+1];
        dp[len] = 1;
        
        for(int i=len-1;i>=0;i--){
            if(s.charAt(i)=='0'){
                dp[i] = 0;
            }else{
                dp[i] = dp[i+1];
            }
            //如果和后面的字符组成的数小于等于26，那么任务当前两个字符是一种解码方法。
            if(i+1<s.length() && (s.charAt(i)=='1' || (s.charAt(i)=='2' && s.charAt(i+1)<='6'))){
                dp[i]+=dp[i+2];
            }
        }
        return dp[0];
    }
  public static void main(String[] args) {
    String str = "26";
    DecodeWays decodeWays = new DecodeWays();
    System.out.println(decodeWays.numDecodings(str));
}
}
